package org.example.leetCode;

/**
 * 343. 整数拆分
 * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
 * 返回 你可以获得的最大乘积 。
 */
public class Code343 {
    /**
     * 贪心算法：
     * 尽可能多地拆分出因子 3，因为数学上证明拆分出尽可能多的 3 可以使乘积最大化。
     * 当 n 大于 4 时，循环减去 3 并将 3 相乘到结果中。
     * 当循环结束时，剩下的 n 值小于等于 4，直接将其乘以当前结果即可
     * @param n  正整数
     * @return 最大乘积
     */
    public int integerBreak(int n) {
        if(n<=3)return n-1;
        int x=n/3,y=n%3;
        if(y==0)return (int)Math.pow(3,x);
        if(y==1)return (int)Math.pow(3,x-1)*4;
        return (int)Math.pow(3,x)*2;
    }
    /**
     * 动态规划解法：
     * dp[i] 表示将正整数 i 拆分成至少两个正整数的和后，这些正整数的最大乘积。
     * 对于每个数字 i，我们可以选择拆分或不拆分：
     * - 如果拆分成 j 和 (i-j)，可以选择是否继续拆分 (i-j)
     * - 状态转移方程：dp[i] = max{j * (i-j), j * dp[i-j]} for j in [1, i-1]
     *
     * @param n  正整数
     * @return 最大乘积
     */
    public int integerBreak1(int n) {
        // dp[i] 表示数字 i 拆分后的最大乘积
        int[] dp = new int[n + 1];

        // 初始化基础情况
        dp[1] = 1; // 数字1不能拆分，但根据题意至少要拆成两个数，所以实际上dp[1]不会直接使用

        // 填充dp数组
        for (int i = 2; i <= n; i++) {
            // 对于每个数字i，尝试所有可能的拆分方式
            for (int j = 1; j < i/2; j++) {
                // 比较两种情况：
                // 1. 直接拆分成 j 和 (i-j)，不继续拆分：j * (i-j)
                // 2. 拆分成 j 和 (i-j)，并继续拆分 (i-j)：j * dp[i-j]
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}
